# 72. 编辑距离 
# https://leetcode-cn.com/problems/edit-distance/
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if not word1 or not word2:
            return len(word1) + len(word2)
        import functools
        @functools.lru_cache(None)
        def helper(i, j):
            if i == -1 or j == -1:
                return i + j + 2
            elif word1[i] == word2[j]:
                return helper(i - 1, j - 1)
            else:
                inserted = helper(i, j - 1)
                deleted = helper(i - 1, j)
                replaced = helper(i - 1, j - 1)
                return min(inserted, deleted, replaced) + 1
        return helper(len(word1) - 1, len(word2) - 1)

# print(Solution().minDistance("horse", 'ros'))
print(Solution().minDistance("efghp", 'abcd'))